package com.LeetCode.dp.String;

import org.junit.Test;

/**
 * 正则表达式匹配
 */
public class MatchString {

    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j-1) == '*'){
                    if(s.charAt(i-1) != p.charAt(j-2) && p.charAt(j-2) != '.'){
                        dp[i][j] = dp[i][j-2];//跳过 .*
                    }else{
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }
                }
            }
        }
        return dp[n][m];
    }

    @Test
    public void test(){
        String s = "aa";
        String p = "a*";
        System.out.println(isMatch(s,p));
    }
}
